This invention relates generally to computer network transmission systems and, in particular, to those capable of storing and transmitting three-dimensional (3D) models. In addition, the invention also relates to graphics processing and display systems capable of rendering together for display combinations of two-dimensional (2D) and three-dimensional (3D) representations of 3D models consisting of one or more components.
A model is a representation of some (not necessarily all) features of a concrete or abstract entity. See J. D. Foley et al., Computer Graphics: Principles and Practice, Addison-Wesley, 1992, which is herein incorporated by reference in its entirety (herein after Fole92). The purpose of a model of an entity is to allow the visualization and understanding of the structure or behavior of the entity. In particular, computer-based models are those that represent three-dimensional (3D) objects and lend themselves to graphic interpretation. Each model may comprise one or more components that correspond to the various parts of the entity represented by the model.
To transfer a 3D model over a network, its components have to be transferred between computers connected to the network. For example, a popular method of transferring 3D models over networks is using the Virtual Reality Modeling Language (VRML). See R. Carrey and G. Bell, xe2x80x9cThe Annotated VRML 2.0 Reference Manualxe2x80x9d, Addison-Wesley, 1997, herein incorporated by reference in its entirety. Other examples include the transmission of one or more 2D images of a model generated on one or more computers to other computers (see U.S. patent application Ser. No. 09/229,793 to B.-O. Schneider and I. Martin entitled xe2x80x9cMethods and Apparatus for Providing 3D Viewpoint Selection in a Server/Client Arrangementxe2x80x9d, IBM docket number Y0998-493, filed on Jan. 13, 1999), the transmission of a compressed representation of a 3D model (see G. Taubin and J. Rossignac, xe2x80x9cGeometry Compression Through Topological Surgeryxe2x80x9d, ACM Transactions on Graphics, April 1998, pp. 84-115), and the progressive transmission of 3D model data (see H. Hoppe, xe2x80x9cProgressive Meshesxe2x80x9d, Proc. Siggraph ""96, August 1996, pp. 99-108). All of these references are herein incorporated by reference in their entirety. The VRML description of the 3D model, the 2D image(s), the model in compressed form, and the progressive description constitute examples of representations of the model.
A fundamental problem in transmitting a 3D model over a network is that a representation is typically selected apriori and used to transfer the entire model. Thus, the transmission is not adaptive, i.e., it does not take into account differences in environment conditions and capabilities of various computers involved in the transfer. A particular representation may be very suitable for certain system configurations and models of a certain size, while it may cause a significant decrease in performance for others. Recently, people have begun to recognize the importance of adaptive transmission, and attempts to implement corresponding strategies have emerged. See B.-O. Schneider and I. Martin, xe2x80x9cAn Adaptive Framework for 3D Graphics in Networked and Mobile Environmentsxe2x80x9d, Proc. Workshop on Interactive Applications of Mobile Computing (IMC ""98), November 1998, (herein after Schn98) which is herein incorporated by reference in its entirety.
A difficult problem to be solved when implementing adaptive transmission is to determine an optimal combination of representations to be used for transmitting the various components of a 3D model, given multiple constraints and criteria. Once such a combination is found, another problem is to mix and manage the different representations for display purposes. Finally, yet another degree of difficulty is introduced when attempting to determine and manage the various representations dynamically, as changing environment conditions cause the optimal combination to change.
In Schn98 the authors propose an adaptive framework that hosts several transmission methods. The selection of an optimal combination of these methods takes into account user preferences and various system parameters, including server performance, server load, available network bandwidth, client capabilities, and client load. The idea is to divide the transmission of the model into two segments (the first manipulable model and the rest of the model) and apply a design-to-time approach to generate a number of alternatives that combine methods with highest quality, shortest duration, highest interactivity, etc. for each of the segments. (For a description of the design-to-time approach, see A. J. Garvey and V. R. Lesser, xe2x80x9cDesign-to-time Real-Time Schedulingxe2x80x9d, IEEE Transactions on Systems, Man, and Cybernetics, 23(6),1993, pp. 1491-1500, herein incorporated by reference in its entirety.) One of these alternatives is then selected based on a heuristic that takes into account user preferences. This approach has the disadvantages that it assumes an apriori segmentation of the model into transmission segments and it does not provide support for dynamic combination of representations. In addition, it is difficult to define meaningful ratings for the various heuristics used in order to rank the alternatives as required by the design-to-time approach.
A different selective approach is proposed in Computer Network Data Distribution and Selective Retrieval System, U.S. Pat. No. 5,675,721, to A. S. Freedman, M. L. Neri, herein incorporated by reference in its entirety. In this case, objects of a virtual world scattered across a distributed environment are transmitted from a network source to a requesting computer. The data associated with a model is prioritized in the order of its relevance to the user. The virtual scene is represented as a hierarchy of perceivable objects which can be visible, audible, tactile, etc. and in turn, may be composed of other perceivable sub-objects that constitute a more detailed description of the parent object. A detail threshold value is used to control how much information is transmitted over the network, as the user navigates the scene. The approach is limited, however, in that it does not take into account any other parameters of the environment (e.g., bandwidth and load of the transmitting node). Moreover, only a single representation is associated with a perceivable object at each level of the hierarchy.
A number of strategies have been proposed for navigation of complex scenes in non-networked environments (i.e., the model is stored locally, on the computer on which the navigation takes place). These methods address the quality-interactivity tradeoff, i.e., how to navigate through a complex scene at interactive rates while maintaining a meaningful detail level for the visible objects. Typically, these strategies make heavy use of image-based rendering techniques, such as morphing and textured impostors and do not address the issue of how to combine various geometric and image-based representations dynamically in a networked context. See P. W. C. Maciel and P. Shirley, xe2x80x9cVisual Navigation of Large Environments Using Textured Clustersxe2x80x9d, Symposium on Interactive 3D Graphics, 1995, pp. 95-102 (herein after Maci95); S. E. Chen, xe2x80x9cQuickTime VRxe2x80x94An Image-Based Approach to Virtual Environment Navigationxe2x80x9d, Proc. Siggraph ""95, Aug. 1995, pp. 29-38; D. Aliaga, xe2x80x9cVisualization of Complex Models Using Dynamic Texture-Based Simplificationxe2x80x9d, Proc. IEEE Visualization ""96, October 1996, pp. 101-106; and D. Aliaga and A. Lastra, xe2x80x9cArchitectural Walkthroughs Using Portal Texturesxe2x80x9d, Proc. IEEE Visualization ""97, October 1997, pp. 355-362, which are herein incorporated by reference in their entirety.
An object of this invention is an improved system and method for transmitting 3D models over networks.
An object of this invention is an improved system and method for transmitting 3D models adaptively.
An object of this invention is an improved system and method for transmitting 3D models adaptively using a hierarchy of prioritized 3D model component representations.
An object of this invention is an improved system and method for adaptively and dynamically managing (i.e, selecting and combining for transmission and display) multiple representations of components of 3D models.
The present invention is a system, method, and product for adaptive network transmission of 3D models. The models comprise one or more model components and are viewed from a viewpoint that may change in time. A model hierarchy is built, with one or more nodes, by clustering together one or more of the model components based on one or more clustering criteria. One or more representations are associated with each node in the hierarchy. A cost function is associated with the model hierarchy and used to determine a cost of each representation at each node. A visibility of each node in the hierarchy from the current viewpoint is evaluated and associated with the respective node. A contribution of each node to an image of the 3D model to be rendered by one or more of the clients is evaluated. The 3D model hierarchy is traversed to select one or more of the representations to be transmitted to the client using a prioritization scheme that accounts for the visibility and contribution of each respective nodes.